package listbyorder.access001_100.test85;

import java.util.Stack;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/5 9:13
 */
public class Solution1 {

    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int r = matrix.length;
        int c = matrix[0].length;
        int[] temp = new int[c];
        int ans = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (matrix[i][j] == '1') {
                    temp[j]++;
                } else {
                    temp[j] = 0;
                }
            }
            ans = Math.max(ans, largestRectangleArea(temp));
        }
        return ans;
    }

    private int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int cur_height = 0;
        int ans = 0;
        int left;
        int right;
        int len = heights.length;
        for (int i = 0; i < len; ) {
            if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
                stack.push(i);
                i++;
            } else if (heights[i] < heights[stack.peek()]) {
                cur_height = heights[stack.pop()];
                right = i;
                left = stack.isEmpty() ? -1 : stack.peek();
                ans = Math.max((right - left - 1) * cur_height, ans);
            } else {
                i++;
            }
        }
        while (!stack.isEmpty()) {
            cur_height = heights[stack.pop()];
            right = len;
            left = stack.isEmpty() ? -1 : stack.peek();
            ans = Math.max((right - left - 1) * cur_height, ans);
        }
        return ans;
    }
}
